#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>



#include "malgrange.h"

llist* malgrange(Matrix *matrix) {
  /*
   * Prenons comme exemple le graph suivant : 1 - 3 - 5      2 - 4
   * Nous avons donc la matrice :
   * 		1  2  3  4  5
   * 	     1  0  0  0  0  1
   * 	     2  0  0  0  1  0
   * 	     3  0  0  0  0  1
   * 	     4  0  1  0  0  0
   * 	     5  1  0  1  0  0
   */
 
  int compteur_actions = 4; // nombre d'actions effectuees
  int i = 0;
  llist sommets_graph = NULL; // listera tous les sommets du graph, qu'on supprimera petit a petit, permet l'arret du while || EX : sommets_graph = NULL
  int nbsommets = matrix->size;
  llist* CFC = malloc(sizeof(llist)*(nbsommets)); // tableau d'une liste de CFC de la matrice  CFC taille 5
  
  for (i ; i < (nbsommets) ; i++ ) // on remplit la liste des sommets
  {
    sommets_graph = ajouterEnFin(sommets_graph, i); // EX : sommets_graph = 1 - 2 - 3 -4 - 5
    compteur_actions++;
  }
  i = 0;
  while(!estVide(sommets_graph)) // tant qu'il y a un sommet à utiliser comme racine || EX : VRAI car sommets_graph est non vide -- Au 2e passage : VRAI car sommets_graph = 2 - 4 -- Au 3e passage : FAUX donc on sort de la boucle
  {
    int sommet = element_i(sommets_graph, 0)->val; // on prend un sommet au hasard (ici toujours le 0 pour plus de facilités) || EX : sommet = 1 -- Au 2e passage sommet = 2
    CFC[i] = bfs(matrix, sommet); // comme graph non oriente, DFS donne une CFC || EX : CFC[0] = 1 - 5 - 3 -- Au 2e passage CFC[1] = 2 - 4
    
    compteur_actions += 3;
    llist parcours = CFC[i]; // on duplique notre CFC nouvellement créée pour la parcourir || EX : parcours = 1 - 5 - 3 -- Au 2e passage parcours = 2 - 4
    while(parcours != NULL) // tant qu'on a pas parcouru toute la liste
    {
      sommets_graph = supprimerElement(sommets_graph, parcours->val); // on supprime dans sommet graph les sommets presents dans la liste CFC || EX sommets_graph = 2 - 4 -- Au 2e passage sommets_graph = NULL
      parcours = parcours->nxt; // pour la boucle
      compteur_actions += 2;
    }
    i++; // on incremente pour la position dans le tableau
  }
  
  printf("-- Pour information cette fonction a effectue %d actions (a ajouter aux nombres d'actions faites par les fonctions appelees dans celle-ci) --\n\n", compteur_actions+1);
  
  return CFC; // retourne donc le tableau contenant toutes les CFC
  
}


void afficherMalgrange(Matrix *matrix)
{
    llist* mg_res = malgrange(matrix);
    //printf("%d\n",sizeof(&mg_res));
		int i = 0;
		for(i ; i < matrix->size ; i++)
		{
		  if(mg_res[i] != NULL) {
		    printf("CFC Num %d : ",i);
		    afficherListe(mg_res[i]);
		    printf("\n");
		  }
		}
}
